#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3ffffff;
#define maxn 5005
struct Edge{
    int u,v,d;
    Edge(int u, int v, int d):u(u),v(v),d(d){}
};
struct HeapNode{
    int d;
    int u;
    HeapNode(int d, int u) : d(d), u(u){}
    bool operator < (const HeapNode& rhs)const {
        return d > rhs.d;
    }
};

int d[maxn];
vector<Edge> g[maxn];
bool vis[maxn];
void dijkstra(int start, int n)
{
    priority_queue<HeapNode> q;
    fill(d, d+maxn, INF);
    memset(vis, 0, sizeof(vis));
    d[start] = 0;
    q.emplace(HeapNode(0, start));
    while (!q.empty()) {
        HeapNode p = q.top();
        q.pop();
        int u = p.u;
        if (vis[u]) continue;
        vis[u] = true;
        for(int i = 0; i < g[u].size(); i++) {
            Edge e = g[u][i];
            if (d[e.v] > d[u] + e.d){
                d[e.v] = d[u] + e.d;
                q.push(HeapNode(d[e.v], e.v));
            }
        }
    }
}

int main() {
    int n, m, cost;
    int u, v;
    cin >> n >> m; // 注意 while 处理多个 case
    for(int i = 0; i < m; i++){
        cin>>u>>v>>cost;
        g[u].emplace_back(Edge(u,v,cost));
        g[v].emplace_back(Edge(v,u,cost));
    }
    dijkstra(1, n);
    if (d[n] == INF){ cout<< -1<<endl;}
    else cout<<d[n]<<endl;
}
// 64 位输出请用 printf("%lld")